class Solution {
public:
    int largestRectangleArea(vector<int>& a) {
        int n=a.size();
        int st[n];
        int r=0;        //指向栈顶元素下一位
        int MSize=0;
        int cur,left;
        for(int i=0;i<n;i++)
        {
            //出栈
            //栈顶元素>=要进的
            while(r>0&&a[st[r-1]]>=a[i])
            {
                cur=st[--r];                    //栈顶元素
                left=r==0?-1:st[r-1];           //底部的左
                MSize=max(MSize,a[cur]*(i-left-1));//面积：底乘高
            }
            st[r++]=i;
        }
        //如果栈里还有元素
        while(r>0)
        {
            cur=st[--r];
            left=r==0?-1:st[r-1];
            MSize=max(MSize,a[cur]*(n-left-1));//（用n来减）底乘高
        }
        return MSize;
    }
};